WORST_CASE(?,O(n^1))
* Step 1: Ara WORST_CASE(?,O(n^1))
    + Considered Problem:
        - Strict TRS:
            anyEq#2(x2,Nil()) -> False()
            anyEq#2(x6,Cons(x4,x2)) -> ite#3(eqNat#2(x6,x4),anyEq#2(x6,x2))
            eqNat#2(0(),0()) -> True()
            eqNat#2(0(),S(x20)) -> False()
            eqNat#2(S(x20),0()) -> False()
            eqNat#2(S(x4),S(x2)) -> eqNat#2(x4,x2)
            ite#3(False(),x4) -> x4
            ite#3(True(),x4) -> True()
            ite2#3(False(),x48,x56) -> x56
            ite2#3(True(),x48,x56) -> x48
            leqNat#2(x8,0()) -> True()
            leqNat#2(0(),S(x16)) -> False()
            leqNat#2(S(x4),S(x2)) -> leqNat#2(x4,x2)
            lookup#2(x10,Node(Cons(x8,x6),ConsTree(x4,x2))) -> ite2#3(leqNat#2(x10,x8)
                                                                     ,lookup#2(x10,x4)
                                                                     ,lookup#2(x10,Node(x6,x2)))
            lookup#2(x2,Node(Nil(),NilTree())) -> bot[0]()
            lookup#2(x4,Leaf(x2)) -> anyEq#2(x4,x2)
            lookup#2(x6,Node(Cons(x4,x2),NilTree())) -> bot[1]()
            lookup#2(x6,Node(Nil(),ConsTree(x4,x2))) -> lookup#2(x6,x4)
            main(x2,x1) -> lookup#2(x2,x1)
        - Signature:
            {anyEq#2/2,eqNat#2/2,ite#3/2,ite2#3/3,leqNat#2/2,lookup#2/2,main/2} / {0/0,Cons/2,ConsTree/2,False/0,Leaf/1
            ,Nil/0,NilTree/0,Node/2,S/1,True/0,bot[0]/0,bot[1]/0}
        - Obligation:
            innermost runtime complexity wrt. defined symbols {anyEq#2,eqNat#2,ite#3,ite2#3,leqNat#2,lookup#2
            ,main} and constructors {0,Cons,ConsTree,False,Leaf,Nil,NilTree,Node,S,True,bot[0],bot[1]}
    + Applied Processor:
        Ara {araHeuristics = NoHeuristics, minDegree = 1, maxDegree = 2, araTimeout = 5, araRuleShifting = Nothing}
    + Details:
        Signatures used:
        ----------------
          0 :: [] -(0)-> "A"(0)
          0 :: [] -(0)-> "A"(3)
          0 :: [] -(0)-> "A"(4)
          Cons :: ["A"(4) x "A"(4)] -(4)-> "A"(4)
          Cons :: ["A"(6) x "A"(6)] -(6)-> "A"(6)
          ConsTree :: ["A"(6) x "A"(6)] -(6)-> "A"(6)
          False :: [] -(0)-> "A"(2)
          False :: [] -(0)-> "A"(0)
          False :: [] -(0)-> "A"(15)
          Leaf :: ["A"(6)] -(6)-> "A"(6)
          Nil :: [] -(0)-> "A"(4)
          Nil :: [] -(0)-> "A"(6)
          NilTree :: [] -(0)-> "A"(6)
          Node :: ["A"(6) x "A"(6)] -(0)-> "A"(6)
          S :: ["A"(3)] -(3)-> "A"(3)
          S :: ["A"(0)] -(0)-> "A"(0)
          S :: ["A"(4)] -(4)-> "A"(4)
          True :: [] -(0)-> "A"(2)
          True :: [] -(0)-> "A"(0)
          True :: [] -(0)-> "A"(15)
          anyEq#2 :: ["A"(0) x "A"(4)] -(4)-> "A"(14)
          bot[0] :: [] -(0)-> "A"(13)
          bot[1] :: [] -(0)-> "A"(13)
          eqNat#2 :: ["A"(0) x "A"(3)] -(1)-> "A"(15)
          ite#3 :: ["A"(2) x "A"(14)] -(1)-> "A"(14)
          ite2#3 :: ["A"(0) x "A"(7) x "A"(7)] -(2)-> "A"(7)
          leqNat#2 :: ["A"(0) x "A"(4)] -(2)-> "A"(9)
          lookup#2 :: ["A"(0) x "A"(6)] -(1)-> "A"(7)
          main :: ["A"(6) x "A"(8)] -(8)-> "A"(0)
        
        
        Cost-free Signatures used:
        --------------------------
        
        
        
        Base Constructor Signatures used:
        ---------------------------------
          "0_A" :: [] -(0)-> "A"(1)
          "ConsTree_A" :: ["A"(1) x "A"(1)] -(1)-> "A"(1)
          "Cons_A" :: ["A"(1) x "A"(1)] -(1)-> "A"(1)
          "False_A" :: [] -(0)-> "A"(1)
          "Leaf_A" :: ["A"(1)] -(1)-> "A"(1)
          "NilTree_A" :: [] -(0)-> "A"(1)
          "Nil_A" :: [] -(0)-> "A"(1)
          "Node_A" :: ["A"(1) x "A"(1)] -(0)-> "A"(1)
          "S_A" :: ["A"(1)] -(1)-> "A"(1)
          "True_A" :: [] -(0)-> "A"(1)
          "bot[0]_A" :: [] -(0)-> "A"(1)
          "bot[1]_A" :: [] -(0)-> "A"(1)
        

WORST_CASE(?,O(n^1))